#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include "SequenceST.h"
#include "FileOps.h"


using namespace std;


template<typename KEY, typename VALUE>
class BST {

private:
    struct Node {
        KEY key;
        VALUE value;
        Node *left;
        Node *right;

        //结构体构造函数
        Node(KEY key, VALUE value) {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }

        //节点复制
        Node(Node *node) {
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
        }
    };

    Node *root;
    int count;

    /**
     * 递归
     * 为根节点为node的二叉搜索树中，插入节点（key,value）
     * 返回插入后二叉树的根
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    Node *insert(Node *pNode, KEY key, VALUE value) {

        if (pNode == NULL) {
            count++;
            return new Node(key, value);
        }

        //根节点key == 要插入的节点key， 执行数据更新
        //执行数据更新,先判断新插入节点的value是否等于源节点（node）的value
        if (pNode->key == key && pNode->value != value) {
            pNode->value = value;
        } else if (key < pNode->key) {
            pNode->left = insert(pNode->left, key, value);
        } else {       //key>node->key
            pNode->right = insert(pNode->right, key, value);
        }

        return pNode;
    }

    /**
     * 非递归插入节点
     *
     * @param key
     * @param value
     */
    Node *insert1(Node *pNode, KEY key, VALUE value) {

        while (pNode != NULL) {
            if (key == pNode->key && value != pNode->value) {
                pNode->value = value;
                break;
            }

            if (key < pNode->key) {
                pNode = pNode->right;
            } else {
                pNode = pNode->right;
            }
        }

        return pNode = new Node(key, value);
    }

    //查找是否包含key节点
    bool contain(Node *pNode, KEY key) {

        if (pNode == NULL) {
            return false;
        }

        if (key == pNode->key) {
            return true;
        } else if (key < pNode->key) {
            return contain(pNode->left, key);
        } else {
            return contain(pNode->right, key);
        }
    }

    VALUE *search(Node *pNode, KEY key) {

        if (pNode == NULL) {
            return NULL;
        }

        if (key == pNode->key) {
            //返回value 的地址！！要加取地址符
            return &pNode->value;
        } else if (key < pNode->key) {
            return search(pNode->left, key);
        } else {
            return search(pNode->right, key);
        }
    }

    void perOrder(Node *node) {

        if (node != NULL) {
            cout << node->key << " ";

            perOrder(node->left);
            perOrder(node->right);
        }
    }

    void inOrder(Node *node) {

        if (node != NULL) {
            inOrder(node->left);
            cout << node->key << " ";
            inOrder(node->right);
        }
    }

    void postOrder(Node *node) {

        if (node != NULL) {
            postOrder(node->left);
            postOrder(node->right);
            cout << node->key << " ";
        }
    }

    void destroy(Node *node) {

        if (node != NULL) {
            destroy(node->left);
            destroy(node->right);
            delete node;
            count--;
        }
    }

    void levelOrder(Node *node) {
        assert(node != NULL);
        queue<Node *> q;
        q.push(node);

        while (!q.empty()) {
            Node *node = q.front();
            q.pop();
            cout << node->key << " ";

            if (node->left != NULL) {
                q.push(node->left);
            }
            if (node->right != NULL) {
                q.push(node->right);
            }
        }
    }

    Node *minimum(Node *node) {

        if (node->left == NULL) {
            return node;
        }

        return minimum(node->left);
    }

    Node *maxmum(Node *node) {
        if (node->right == NULL) {
            return node;
        }

        return minimum(node->right);
    }

    Node *removeMin(Node *node) {

        if (node->left == NULL) {
            Node *node1 = node->right;

            delete node;
            count--;
            return node1;
        }

        node->left = removeMin(node->left);
        return node;
    }

    Node *removeMax(Node *node) {
        if (node->right == NULL) {
            Node *node1 = node->left;

            delete node;
            count--;
            return node1;
        }

        node->right = removeMax(node->right);
        return node;
    }

    Node *remove(Node *node, KEY key) {

        if (node != NULL) {

            if (key < node->key) {

                node->left = remove(node->left, key);
            } else if (key > node->key) {
                node->right = remove(node->right, key);
            } else {
                if (!node->left) {
                    Node *rightNode = node->right;
                    delete node;
                    count--;
                    return rightNode;
                }

                if (!node->right) {
                    Node *leftNode = node->left;
                    delete node;
                    count--;
                    return leftNode;
                }

                Node *successor = new Node(minimum(node->right));
                count++;
                successor->right = removeMin(node->right);
                successor->left = node->left;
                delete node;
                count--;
                return successor;
            }
        } else {
            return NULL;
        }
    }

public:
    BST() {
        root = NULL;
        count = 0;
    }


    virtual ~BST() {

        destroy(root);
    }

    bool isEmpty() {
        return count == 0;
    }

    /**
     * 插入节点
     * @param key
     * @param value
     */
    void insert(KEY key, VALUE value) {

        //递归插入
        root = insert(root, key, value);

        //非递归
        //root = insert(root,key,value);
    }


    bool contain(KEY key) {
        return contain(root, key);
    }


    VALUE *search(KEY key) {
        return search(root, key);
    };


    void perOrder() {
        perOrder(root);
    }


    void inOrder() {
        inOrder(root);
    }


    void postOrer() {
        postOrder(root);
    }


    void levelOrder() {
        levelOrder(root);
    }


    KEY minimum() {
        assert(count != 0);
        Node *node = minimum(root);
        return node->key;
    }


    KEY maxmum() {
        assert(count != 0);
        Node *node = maxmum(root);
        return node->key;
    }

    void removeMin() {
        if (root) {
            root = removeMin(root);
        }
    }

    void removeMax() {
        if (root) {
            root = removeMax(root);
        }
    }

    void remove(KEY key) {
        root = remove(root, key);
    }
};

int main() {

    return 0;
}